Valda: Note the proverb Не сразу Москва строилась! -- Moscow wasn't built all at once!

Рим не за день построили ("Not by the end of [only] a day did they build Rome") is also well-known with slight variants in the phrasing, but AFAIK it's considered a borrowing from either English or French -- not a "native" expression.