Karelina ir izcelsmes no krievu uzvārda "Карелин". Tas visbiežāk saistīts ar slaveno krievu cīkstoni Aleksandru Karelinu — leģendāru grieķu-romiešu cīkstoni, trīskārtēju Olimpisko čempionu, 9-kārtēju pasaules čempionu, kas pazīstams ar savu neuzvarēto sēriju vairāk nekā 13 gadus.
Vēsturiski uzvārds var būt saistīts ar ģeogrāfisku nosaukumu — piemēram, Krievijas ziemeļos esošo Karelijas reģionu, tāpēc tas varētu nozīmēt "cilvēks no Karelijas" vai arī būt cēlies no personvārda "Karels" vai "Karls". Dažos avotos minēts, ka tas varētu būt radniecīgs vārdam "Karalis" senajā izrunā.
Citi ievērojami cilvēki ar šo uzvārdu:
- Jekaterina Karelina — krievu aktrise.
- Irina Karelina — krievu daiļslidotāja un trenere.
Tātad, Karelina galvenokārt asociējas ar Aleksandru Karelinu un var būt saistīts ar Karelijas reģionu vai vēsturiskiem personvārdiem.