Molenaar begon bij ZVV Zilvermeeuwen en speelde één jaar in de jeugd bij AZ. Hij keerde terug bij De Zilvermeeuwen en speelde daar in het eerste elftal. Hij haalde het Nederlands amateurelftal en werd aangetrokken door FC Volendam.
Hij is gecontracteerd bij Leeds United door de toenmalige manager George Graham. Hij ging over van FC Volendam voor 1 miljoen Britse ponden (wat nu overeenkomt met ongeveer 1,3 miljoen euro). Dit gebeurde in januari 1997 voor de versterking van de verdediging bij Leeds United. Aan het eind van het seizoen 1996/97 werd hij vaste basisspeler. In het seizoen 1997/98 werd hij niet meer opgesteld en alleen nog als wissel ingezet voor halve wedstrijden. In het seizoen 1998/99 werd hij verkozen boven David Wetherall en werd hij weer ingezet als basisspeler. Dit veranderde door een opstootje met Nicolas Anelka die op dat moment speelde voor Arsenal. Daarna werd hij geplaagd door een blessure aan zijn gewrichtsband. Hij herstelde weer in 2000, maar maakte geen indruk meer en werd mede daardoor in de zomer van 2001 verkocht aan Bradford City. Hier moest hij helpen om degradatie te voorkomen. Hij bleef daar tot 2003. Zijn contract werd niet verlengd en RBC Roosendaal nam hem over. Hij is vader van drie kinderen.
Bij Leeds kreeg hij zijn bijnaam The Terminator van de fans vanwege zijn forse lichaam en zijn lengte.
Molenaar werd jeugdtrainer bij AZ en trainde in het seizoen 2011/12 de A1. In het seizoen 2010/11 liep hij stage bij SBV Excelsior onder Alex Pastoor. Vanaf medio 2012 was hij assistent van Pastoor bij N.E.C.[2] Nadat Pastoor in augustus 2013 ontslagen werd, vertrok Molenaar enkele dagen later bij N.E.C.[3] In het seizoen 2014/15 trainde hij RKSV Halsteren. Vanaf het seizoen 2015/16 werd Molenaar hoofdtrainer van FC Volendam. In zijn eerste seizoen haalde Molenaar met de Volendammers de nacompetitie. Op 22 maart 2017 maakte hij bekend aan het einde van het seizoen 2016/17 te vertrekken bij de club uit het palingdorp.[4] Op 24 april 2017 werd hij ontslagen. In juni 2017 werd hij aangesteld als hoofdtrainer van Roda JC Kerkrade. Hij tekende een contract voor één seizoen, met een optie voor een tweede seizoen. Op 19 maart 2019 werd Molenaar ontslagen bij Roda JC. Op 18 juni 2019 werd bekendgemaakt dat Robert Molenaar de nieuwe trainer zou worden bij Almere City. Daar tekende hij voor twee seizoenen.[5][6] Hier werd hij tijdens zijn eerste seizoen voortijdig ontslagen.
In de zomer van 2021 werd hij trainer van het onder 21-elftal van NAC Breda. Op 15 juni 2022 werd bekendgemaakt dat hij de nieuwe hoofdtrainer werd van het eerste elftal, dat toen uitkwam in de Keuken Kampioen Divisie. Op 27 december 2022 heeft NAC Breda besloten niet verder te gaan met hem als hoofdtrainer.[7]
Nederland
Leeds United