Początki regularnej komunikacji pocztowej sięgają czasów panowania Zygmunta Augusta. Po śmierci swej matki, królowej Bony Sforza, władca ten uruchomił stałe połączenie między Krakowem i Wenecją przez Wiedeń i Graz (18 X 1558 r.). Jedną z przesłanek, jaką kierował się Zygmunt August, była potrzeba utrzymywania stałego kontaktu z Wenecją, gdzie toczył się proces o spadek po zmarłej królowej. Głównym powodem była jednak konieczność utrzymywania regularnych kontaktów dyplomatycznych z państwami europejskimi. Samo połączenie pocztowe zorganizowano na wzór tych, które funkcjonowały na zachodzie Europy. Przebieg poczty z Krakowa do Wenecji wynosi 10 dni, a z Wenecji do Wiednia 5 dni. Przesyłki królewskie były zwolnione z opłat. Kursy odbywały się najpierw co tydzień, później dwa razy w miesiącu. Od 1562 roku dopuszczono do obrotu również korespondencję prywatną przy wykorzystaniu oficjalnego połączenia królewskiego, co miało związek przede wszystkim z faktem niskiej rentowności poczty.
Samą organizację poczty w Polsce zawdzięczamy Włochom. Pierwszym jej zwierzchnikiem został w 1558 roku Prosper Prowana, który rok wcześniej otrzymał szlachecki indygenat. Przywilej, którym przekazano pocztę Prowanie, nakazywał odprowadzać uzyskane dochody do skarbu Zygmunta Augusta, a rachunki i wydatki przedstawiać królowi. Prowana zarządzał pocztą, a za swoją pracę otrzymywał rocznie 300 florenów. Naczelny nadzór nad pocztą przysługiwał królowi, który opłacał również kursorów i koszty utrzymania koni. Zygmunt August przydzielił Prowanie dom w Krakowie, z przeznaczeniem na pocztę i zwolnił go od obowiązku świadczenia ciężarów publicznych. Pracownicy pocztowi byli ubrani w stroje z herbem królewskim i objęci immunitetem. Obowiązywała zasada tajemnicy korespondencji królewskiej; przesyłki prywatne natomiast mogły być poddawane rewizji urzędników państwowych. W 1562 roku, po ustąpieniu Prowany, dyrektorem poczty został Krzysztof Taxis, dawny pocztmistrz augsburski oraz nadworny pocztmistrz cesarski. Poczta z Krakowa do Wenecji docierała w ciągu 10 dni, z Krakowa do Wilna natomiast w ciągu 7, a nawet 5 dni. Osoby prywatne płaciły za jej przewożenie z Krakowa do Wiednia 3 gr. (równowartość 60 jaj, 2 kur lub ¼ korca pszenicy) od 1 łuta wagi (12,672 g), natomiast z Krakowa do Wenecji – 6 gr. od 1 łuta wagi. Taxis otrzymywał 1500 talarów pensji rocznej i był zobowiązany przewozić nieodpłatnie przesyłki królewskie nie tylko do Krakowa i Wilna, lecz również do Rzymu, Neapolu, Hiszpanii oraz innych krajów europejskich.
Następcą Taxisa byli kolejno mieszczanin krakowski włoskiego pochodzenia Piotr Maffon (w latach 1564 – 1569) oraz krakowski bankier Sebastian Montelupi (od 1569 roku). Za Montelupiego poczta z Krakowa do Wenecji była przesyłana co tydzień, a na Litwę co 3 tygodnie. Król płacił Montelupiemu rocznie 1300 talarów, a wydatki na utrzymanie poczty pokrywano z opłat uzyskiwanych z tytułu przyjmowania i doręczania korespondencji prywatnej.
Z czasów Zygmunta Augusta pochodzą również dwie bardzo ważne konstytucje sejmowe dotyczące komunikacji. Na sejmie 1564 roku uchwalono tzw. „Uniwersał Podwodny Warszawski”, będący najstarszą ordynacją pocztową na ziemiach polskich. Określiła ona obowiązki podwodowe (miasta obciążone obowiązkiem podwód miały je udostępniać za pieniądze pochodzące ze składek uiszczanych rocznie przez starostów do skarbu królewskiego) oraz najdawniejszą polską taryfę pocztową.
W zasadniczej części konstytucja ta nie różniła się od obowiązującego wcześniej zwyczaju, z tą jednak różnicą, że właściciele każdej włóki ziemi zostali zobowiązani do posiadania 2 koni lub takowe powinni hodować wójtowie lub sołtysowie. Doprecyzowała więc ona dawne prawa wprowadzając m. in. zasadę wynajmowania koni za pieniądze znajdujące się w skarbcu królewskim (jeśliby brakowało ich na tzw. odwóz królewski w miejscowości zobowiązanej udzielać podwód) oraz obowiązek utrzymywania w należytym porządku dróg, na co zresztą zwracały uwagę także uchwalane wcześniej konstytucje. Wynajmowanie koni przez urzędników z pominięciem poczty królewskiej (np. we wsi lub u podróżnego) było możliwe tylko wtedy, gdy koń padł w drodze.
Uzupełnienie powyższej konstytucji stanowił wydany na sejmie w Piotrkowie Trybunalskim tzw. „Uniwersał piotrkowski” z 1565 roku. Ze względu na małe wpływy z poczty, będące konsekwencją zbyt wygórowanych cen za podwód według taryfy ustanowionej w 1564 roku, zmieniono stawki, co wpłynęło korzystnie na wzrost przychodów.