Liwa al-Quds (Jerusalem Brigade) sa att Abdullah Issa bara var en 12-åring från en fattig flyktingfamilj som bodde i ett rebelliskt område i Aleppo.
Medlemmar av Nour al-Din al-Zinki-rörelsen anklagas för att ha dödat honom.
Det sade att de ansvariga överlämnades till en rättslig kommitté och fördömde mordet som ett "våld".
USA, som tidigare har tillhandahållit militärt stöd till Nour al-Din al-Zinki-rörelsen, sade att man sökte mer information om vad det beskrev som "en skrämmande rapport".
"Om vi kan bevisa att detta verkligen var vad som hände och denna grupp var inblandad... det skulle ge oss paus om någon hjälp eller, ärligt talat, någon ytterligare inblandning med denna grupp," statliga avdelningen talesman Mark Toner berättade reportrar.
Två korta videor dök upp online på tisdag morgon visar en pojke hånas och sedan halshuggs av en grupp syriska rebeller.
Den första visar det skrämda barnet, som kunde vara så ung som 10, sitter i baksätet på en pick-up lastbil, omgiven av fem män.
En av männen griper honom i håret när de anklagar honom för att vara medlem av Liwa al-Quds, en palestinsk milis som kämpar till stöd för Syriens president Bashar al-Assad och deltog i sammandrabbningar med rebeller på tisdagen i Handarat, norr om Aleppo.
Den andra videon visar mordet på pojken.
Det syriska observatoriet för mänskliga rättigheter sade att pojken greps av rebeller i Handarat, men att mordet ägde rum i Mashhad. Den brittiska övervakningsgruppen kunde inte bekräfta om pojken var palestinsk eller barnsoldat.
Liwa al-Quds gjorde ett uttalande på Facebook där han sade att dess utredning hade funnit att han var en 12-årig palestinsk vid namn Abdullah Issa, som bodde i Mashhad med sin familj.
Det sades också att han tydligen hade fått medicinsk behandling innan han blev beslagtagen, och han lade märke till att ett fotografi visade ett intravenöst dropp i armen.
Liwa al-Quds anklagade rebellerna för att döda barnet bara för att han var palestinsk, för att ta "billig och avskyvärd hämnd" för förluster på slagfälten.
Nour al-Din al-Zinki-rörelsen sade att den fördömde och fördömde "sådana övergrepp", men insisterade på att de var "individuella fel som varken representerar våra typiska metoder eller vår allmänna politik".
"Alla personer som begått överträdelsen har kvarhållits och överlämnats till [rättslig] kommitté för utredningar i enlighet med relevanta rättsliga normer", tillade den.
Tidigare denna månad publicerade Amnesty International en rapport om en rad överträdelser som påstås ha begåtts av Nour al-Din al-Zinki-rörelsekämpar i Aleppo, inklusive bortföranden och tortyr.
En palestinsk pojke som filmades och halshöggs av syriska rebeller i tisdags var ingen kämpe, sade en regeringsvänlig palestinsk milis.