A Kr.e. 8. év márciusában (József és Mária házasságkötésének havában) Cézár Augusztusz elrendelte, hogy a római birodalom minden lakosát számlálják meg, hogy az adóztatás hatékonyabbá tételéhez is felhasználható népszámlálást kell tartani. A zsidók mindig is előítélettel viseltettek mindenféle kísérlettel szemben, mely „a nép megszámlálására” irányult, és ez a Heródessel, Júdea királyával kapcsolatos komoly hazai nehézségekkel együtt oda vezetett, hogy a zsidó királyságban egy évvel elhalasztották a népszámlálást. Az egész római birodalomban Kr.e. 8-ban tartották meg a népszámlálást, kivéve Heródes palesztinai királyságát, ahol egy évvel később, Kr.e. 7-ben került rá sor.
Nem volt szükség arra, hogy az összeírásra Mária is elutazzon Betlehembe—József ugyanis fel volt hatalmazva a családja bejegyeztetésére is—de Mária, lévén kalandvágyó és erélyes személy, ragaszkodott ahhoz, hogy vele tartson. Félt egyedül maradni, attól tartott, hogy esetleg a gyermek József távolléte alatt születik meg, és megint csak utalunk arra, hogy Betlehem nem esett messze Júda városától, ezért Mária a nőrokonánál, Erzsébetnél teendő várhatóan kellemes látogatásnak nézett elébe.
József tulajdonképpen megtiltotta Máriának, hogy vele tartson, de hiába; amikor a három-négy napos útra az élelmet csomagolták, Mária kétannyi adagot készített és csomagolt. De még mielőtt ténylegesen is útnak indultak volna, József megbékélt a gondolattal, hogy Mária is jön, és hajnalban jókedvűen indultak el Názáretből.
József és Mária szegény volt, és mivel csak egy teherhordóállatuk volt, ezért Mária, várandós lévén, az állaton ült és az állat vitte a csomagjukat is, míg József gyalogolva vezette az állatot. Egy otthon felépítése és berendezése nagy érvágás volt József számára, hiszen hozzá kellett járulnia a szülei támogatásához is, lévén, hogy az apja nem sokkal azelőtt vált munkaképtelenné. E zsidó házaspár a szerény hajlékukból tehát Kr.e. 7. augusztus 18-án reggel indult el s vette útját Betlehem felé.
Az utazással töltött első napjuk során eljutottak a Gilboa-hegy lábához, ahol éjszakára letáboroztak a Jordán folyó mellett és mindenféle elképzeléseket gyártottak arról, hogy milyen fiuk fog születni, József tartotta magát a szellemi tanító képzetéhez, Mária pedig kitartott egy zsidó Messiás, a héber nemzet megszabadítójának eszméje mellett.
Az augusztus 19-i verőfényes, korai reggelen József és Mária már újból úton volt. Ebédjüket a Szartaba-hegy lábánál költötték el, mely a Jordán völgyére nézett, onnan továbbhaladtak, Jerikóban töltve az éjszakát, ahol egy fogadóban szálltak meg a város peremén, a főút mellett. Estebéd után, és miután sokat vitatkoztak a római uralom elnyomó jellegéről, Heródesről, a népszámlálási összeírásról és arról a viszonylagos befolyásról, melyet Jeruzsálem és Alexandria, mint két központ fejtett ki a zsidó tudományokra és műveltségre, a názáreti utazók nyugovóra tértek. Augusztus 20-án kora reggel folytatták útjukat, még dél előtt elérték Jeruzsálemet, ahol is elmentek a templomba, és úti céljukat követve a délután közepe táján érkeztek meg Betlehembe.
A fogadó már tömve volt, és József emiatt a távoli rokonoknál próbált meg szállást keresni, de Betlehemben minden szoba tele volt. A fogadó udvarába visszatérve arról értesült, hogy a csoportos utazók számára fenntartott aklokból, melyeket a szikla oldalába vájva alakítottak ki és amelyek épp a fogadó alatt helyezkedtek el, elvitték az állatokat és a szállást keresők részére ki is takarították. A szamarat az udvarban hagyva József a vállára vette a ruhás és eleséges csomagjaikat és Máriával együtt a kőlépcsőn a lenti szálláshelyükre ment. Egy korábban magtárnak használt helyen találták magukat, épp szemben az aklokkal és a jászlakkal. Itt sátorlapokat függesztettek fel, és szerencsésnek mondhatták magukat, hogy ilyen kényelmes szállásuk lehet.
József arra gondolt, hogy nyomban felkerekedik és feliratkozik, de Mária kimerült volt; igen fáradtnak érezte magát és arra kérte a férjét, hogy maradjon mellette, mely kérésnek ő eleget is tett.