Từ đó, ngài tiến vào vùng Phrygia, băng qua hồ Ascania, nơi muối tự kết tinh một cách tự nhiên. Người bản địa sử dụng loại muối này và hoàn toàn không cần đến muối biển. Vào ngày hành quân thứ năm, ngài tới Celaenae, một thành phố có vách đá kiên cố dựng đứng tứ bề. Thành trì này đang bị viên phó vương xứ Phrygia cùng một đội quân gồm 1.000 lính Carian và 100 lính đánh thuê người Hy Lạp chiếm giữ. Họ cử các sứ giả đến gặp Alexander, hứa sẽ đầu hàng nếu không nhận được viện binh trước một ngày đã thỏa thuận, và họ đã nêu đích danh ngày đó. Với Alexander, thỏa thuận này có lợi hơn việc bao vây vách đá kiên cố vốn bất khả xâm phạm từ mọi phía. Tại Celaenae, ngài để lại một đội quân đồn trú gồm 1.500 lính. Sau khi ở lại đây mười ngày, ngài bổ nhiệm Antigonus, con trai của Philip, làm phó vương xứ Phrygia; đặt Balacrus, con trai của Amyntas, làm tổng chỉ huy lực lượng đồng minh Hy Lạp thay cho Antigonus, rồi ra lệnh tiếp tục hành quân đến Gordium. Ngài gửi lệnh cho Parmenio tập hợp tại đó cùng với lực lượng dưới quyền; vị tướng này đã tuân theo mệnh lệnh. Những người lính mới cưới từng được cử về Macedonia nay cũng đã tới Gordium, đi cùng họ là một đạo quân khác được chiêu mộ dưới sự chỉ huy của Ptolemy con trai Seleucus, Coenus con trai Polemocrates, và Meleager con trai Neoptolemus. Đạo quân này gồm 3.000 bộ binh Macedonia, 300 kỵ binh Macedonia, 200 kỵ binh Thessaly, và 150 lính Elea dưới sự chỉ huy của Alcias người Elea.

Gordium nằm ở vùng Phrygia gần Hellespont, tọa lạc bên bờ sông Sangarius. Con sông này bắt nguồn từ Phrygia, chảy qua vùng đất của người Thracian xứ Bithynia rồi đổ ra Biển Đen. Tại đây, một phái đoàn từ Athens đến gặp Alexander, khẩn cầu ngài trả tự do cho các tù binh người Athens từng bị bắt giữ bên sông Granicus khi đang chiến đấu cho quân Ba Tư; lúc đó họ đang bị giam cầm trong xiềng xích tại Macedonia cùng với hai ngàn người khác bị bắt trong trận đánh đó. Các sứ giả ra về mà chưa đạt được nguyện vọng cho các tù binh vào thời điểm này. Bởi lẽ, Alexander cho rằng không an toàn khi cuộc chiến chống lại người Ba Tư vẫn đang tiếp diễn, nên ngài không muốn giảm bớt dù chỉ một chút nỗi sợ hãi mà ngài gieo rắc lên những người Hy Lạp, những kẻ vốn không cảm thấy hổ thẹn khi phục vụ như lính đánh thuê cho người ngoại bang để chống lại chính Hy Lạp. Tuy nhiên, ngài trả lời rằng khi nào cuộc chinh phạt hiện tại đạt được thành công, họ có thể đến như những sứ giả để đàm phán thay cho những người đó.