„Nicoloso da Recco” należał do dwunastu włoskich wielkich niszczycieli typu Navigatori, nazwanego tak z powodu noszenia przez okręty imion włoskich żeglarzy. Zostały one zaprojektowane jako okręty o silnym uzbrojeniu artyleryjskim i wysokiej prędkości, aby przeciwstawić się wielkim niszczycielom francuskim. Zamówienie na budowę okrętów zostało złożone w 1926 roku. „Nicoloso da Recco” był zbudowany w stoczni Cantieri Navali Riuniti (CNR) w Ankonie, razem z niszczycielem „Emanuele Pessagno”. Wszystkie okręty zostały wciągnięte na listę floty dekretem królewskim z 23 czerwca 1927 roku, klasyfikowane wówczas jako niszczyciele, a 19 lipca 1929 roku przeklasyfikowano je na „zwiadowców” (wł. esploratori). 5 września 1938 roku okręty typu Navigatori przeklasyfikowano z powrotem na niszczyciele (cacciatorpedinieri).
Stępkę pod budowę „Nicoloso da Recco” położono 14 grudnia 1927 roku, , , . Otrzymał imię na cześć XIV-wiecznego genueńskiego żeglarza , badacza Atlantyku. Roboty w stoczni się przeciągnęły i okręt wodowano 5 stycznia 1930 roku. 3 kwietnia 1930 roku okręt przechodził próby prędkości. Został ukończony i wcielony do służby 20 maja 1930 rokuOdmiennie podaje datę wejścia do służby 10 marca 1930 roku, być może omyłkowo (taką samą jak dla „Emanuele Pessagno”)..