Det var söt hämnd för Nigeria vars senior sida förlorade 3-2 till Claude Le Roy's Congo förra året i en 2015 Afrika Cup of Nations kval - ett resultat som slutligen förnekade Super Eagles en plats i finalen och en chans att försvara sin titel.
Nigeria skryter med en stolt OS fotboll rekord, efter att ha vunnit guld medaljer vid Atlanta Games 1996.
De avslutade också löpare-up vid 2008 Peking OS, där nuvarande Nigeria under-23 coach Samson Siasia (bildad) också coachade "Dream Team" i Kina.
På söndagen, det var Junior Ajayi som visade sig vara Siasias match vinnare, poäng båda målen strax efter halvtid, framför 35,000 hemma fans.
Le Roy's Congo drog en tillbaka i 68: e minuten - men Nigeria höll på att ta den första ben fördel i under-23 nivå tredje-round kval.
Return match är planerad till början av augusti och de totala vinnarna kvalificerar sig för en slutet av året turnering i Senegal från vilken de tre bästa lagen av åtta går till Rio.
På andra håll hjälpte ett sent mål blixten Egypten överväldiga Uganda 4-0.
De Baby faraonerna ledde efter åtta minuter i Alexandria och lagt till ytterligare tre mål under de senaste 15 minuterna för att bygga en enorm första-ben ledning.
Mahmoud 'Kahraba' Abdel Moneim - påsatt en tandställning och Mohamed Salim och Ramadan Sobhy var också på mål.
Egyptiska TV kommentatorer retade Uganda tränare Milutin 'Micho' Sredojevic (bildad) före matchen genom att märka sitt lag en "punching väska".
Det såg ut som om Micho kunde ha det sista skrattet när östafrikanerna återhämtade sig från att falla bakom ett Salimmål och till och med kom nära att jämnas ut kort efter halvtid.
Uganda kapten och ledande målskytt Farouk Miya fann sig själv en-mot-ett med målvakt Mosaad Awad, men misslyckades med att göra mål.
Egypten tränare Hossam El-Badry vände tidvattnet tillbaka till förmån för ett land som har spelat på OS fotbollsturneringar 11 gånger genom att införa mittfältaren Ahmed Rafaat halvvägs genom andra halvan.
Rafaat satte upp mål för "Kahraba" och Sobhy som uganderna vissnade under obeveklig press.
"Kahraba" avslutade rout i stopptid genom avrundning målvakt Omar Salim och stroking bollen över linjen.
Adama Niane blev den ledande målskytten i den afrikanska kvaltävlingen, tog hans totala till fyra mål genom att rycka vinnaren som Mali besegrade Gabon 1-0 i Libreville.
Niane, som är med franska klubben Nantes, fick 13 minuter från tiden.
Gabon var chockvinnare i en OS-turnering i Marocko för fyra år sedan efter att ha eliminerat Mali på vägen.
Zambia tvingade en 0-0 dragning med Elfenbenskusten i Abidjan trots att man måste spela mycket av den andra halvan med 10 män.
Defender Boyd Mkandawire skickades iväg på 62 minuter efter att ha visats ett andra gult kort, men ivorianerna misslyckades med att dra nytta av sin extra man.
Sydafrika, vars tidigare olympiska framträdande var i Sydney för 15 år sedan, drog 1-1 med grannar Zimbabwe på Rufaro Stadium i Harare på söndag.
Keagan Dolly satte Sydafrika framåt i 67: e minuten innan värdar Zimbabwe tilldelades ett straff sju minuter från tiden, med Walter Musona framgångsrikt konvertera.
Sierra Leone medgav två första halvmål eftersom de förlorade 2-0 till Algeriet i Blida.
Det andra benet kommer också att spelas i Blida eftersom Sierra Leone inte kan vara värd för matcher på grund av utbrottet av det dödliga ebolaviruset i landet.
Sierra Leone kommer nominellt att vara värdar för den match som har lagts fram till den 25 juli på begäran av SLFA.
De totala vinnarna kommer att kvalificera sig för African Under-23 Championship i Senegal från 28 november-12 december 2015, med de tre bästa på turneringen som går vidare till OS.
Olympiska kval är begränsade till fotbollsspelare födda den 1 januari 1993 eller efter den 1 januari 1993, med tre överåldersstjärnor tillåtna vid finalen den 3-20 augusti 2016 i Brasilien.
Nigeria kundet närmade sig kvalificering för 2016 Rio Olympics med en 2-1 seger över Kongo Brazzaville i Port Harcourt.