Besøket gir økte forhåpninger om at de to landene kan leve side om side i fred.
Sudan og Sør-Sudan ble i mars enige om å gjenoppta oljeproduksjonen i løpet av kort tid.
Avtalen innebærer at olje produsert i Sør-Sudan igjen kan sendes gjennom rørledningen i Sudan, som i dag er den eneste måten oljen kan skipes ut på.
Avlyst
I 14 måneder sto oljeproduksjonen i Sør-Sudan stille på grunn av oljekonflikten med Sudan.
Begge landene har tapt store summer på produksjonsstansen. Men de to landene har ennå ikke blitt enige om hvem som eier Abyei-provinsen og andre regioner langt den 2.000 kilometer lange grensen.
Bashir hadde planlagt et besøk i Sør-Sudan i fjor, men det ble avlyst på grunn av kamper langs grensen.
Bashir har med seg en stor delegasjon, og han skal diskutere olje og sikkerhetsspørsmål med sin kollega i sør, Salva Kiir.
I gang
– De er nødt til å diskutere administrasjonen av Abyei, sier Sør-Sudans informasjonsminister Barnada Marial Benjamin.
Det gjenstår en rekke uløste territorielle stridsspørsmål og en løsning på hvor mye sør skal betale for å frakte oljen sin gjennom Sudan.
Sør-Sudan har store oljereserver, men er helt avhengig av å få sendt olje gjennom Sudan for å få levert den videre til andre land.
I forrige uke startet sør opp igjen oljeproduksjonen og den første lasten med olje er ventet til Sudans eksportterminal Port Sudan ved Rødehavet i slutten av mai.
Les også: