Недтің әкесі ирландиялық Джон (Рэд) Келли екі шошқаны ұрлағаны үшін, Ван-Димен жеріне (қазіргі Тасманияға) жер аударылған; бес жылғы каторгадан босағаннан кейін, ол Викторияның бір түкпіріне қоныс аударып, жергілікті фермердің қызы әрі ирландиялық Эллен Квиннге үйленді. Нед отбасында үшінші бала (сегіз баланың ішінде) болатын. Ол жергілікті мектепте бастауыш білім алды, күшітілігімен және батылдығымен ерекшеленді (бірде суға батып бара жатқан баланы құтқарды). Нед 12 жасқа толғанда, оның әкесін бұзау ұрлады деп айыптады; алайда бұған дейін жаман атты болғаны болмаса, оны олай айыптауға анайанау айтқан негіз болмаған еді. Джон Келлиді 25 фунт айыппұл төлейді деген шешім шығарылды. Ондай ақшасы болмаған Джон амалдың жоғынан жазасын түрмеде өтейді және сол жерде 1866 жылы 27 желтоқсанда қайтыс болады. Отарлық соттың әділетсіздігі мен қатыгездігі Нед Келлиге қатты әсер етті. Жас кезінде ол әрдайым құтырған мінезі үшін жазаланып жүрді:14 жасында Недті шошқа өсіруші-қытайлықты ұрғаны үшін 10 күнге қамап қойды; 15 жасында ол қаңғыған саудагермен төбелескені үшін және Гарри Пауэр деген қарақшымен ынтымақтасты деген күдікпен аз уақытқа түрмеге түсті. 16 жасында "жас бушрейнджер" деген жаман атаққа ие болған Нед Келли ұрланған атқа мініп жүрген оны қамамақ болған полицей қызметкерін ұрғаны үшін 3 жыл бас бостандығынан айырылды (Нед атты басқа адамнан сұрап алған болатын және ұрлыққа қатысы болмаған). Алайда Недтің аға-інілері тура осыған ұқсас жағдайларда қамауға алынды. БотандыққаБостандыққа шыққаннан кейін Нед ағаларымен, анасымен және өгей әкесі калифорниялық Джорджем Кингпен бірге мал ұрлығын кәсіп ете бастады.
