Powrócił jednak do Medyny dopiero po tym, jak udało mu się nawrócić władcę Omanu na islam.
Jako dowódca jednego z trzech oddziałów wysłanych do Palestyny wziął udział w bitwach pod Adżnadajn (634) i nad rzeką Jarmuk (636), i był odpowiedzialny za zajęcie południowo-zachodniej Palestyny. W roku 639 wraz z czterotysięcznym oddziałem samowolnie wyruszył na Egipt, zdobywając twierdzę Rhinocolura, a w roku 640 Peluzjum. Po fakcie kalif Umar zaakceptował inwazję i przysłał Amrowi posiłki. W lipcu lub sierpniu 640 r. Arabowie zwyciężyli oddziały bizantyjskie w bitwie pod Heliopolisem, a w roku 641 zdobyli główną bizantyjską twierdzę Babilon i zajęli Górny Egipt. Podczas oblężenia Babilonu patriarcha Aleksandrii i jednocześnie namiestnik Egiptu Cyrus prowadził z Arabami negocjacje, jednakże gdy przedstawił cesarzowi Herakliuszowi warunki wynegocjowanego przez siebie traktatu, ten odwołał go ze stanowiska, nie bez podstaw podejrzewając go o zdradę. Po zdobyciu Babilonu Amr pomaszerował w kierunku Aleksandrii. Jej potężne fortyfikacje wydawały się wprawdzie nie do zdobycia, ale arabski wódz wynegocjował poddanie się miasta na korzystnych dla niego warunkach. Arabowie nie wkroczyli do niego, lecz jedynie założyli pod nim obóz wojskowy i ściągnęli kontrybucję. Po śmierci Herakliusza w lutym 641 r.