Старкаду досталось тяжелое наследство. Его дед был великан, который похитил себе в жены принцессу, так что его отец Сторвирк родился больше и сильнее, чем обычные люди. Сторвирк бежал с Унной, дочерью ярла Халогаланда из Северной Норвегии, поскольку родня была против их союза. Братья Унны преследовали беглецов до острова, на котором те поселились, и сожгли дом и хозяев. Каким-то чудом маленький Старкад уцелел в бойне и попал на воспитание к королю Харальду в Агде, на юге Норвегии. Потом Харальда убил король Хордаланда (район современного Бергена), и трехлетнего Старкада усыновил человек со странным именем Хроссхарс-Грани (Грани Конский Волос; имя напоминает о коне Сигурда). Девять лет спустя сын Харальда Викар явился отомстить за отца и нашел Старкада у Хроссхарс-Грани. Юный Старкад оказался бесполезным «поедателем углей». Но зато он был крупный, темнолицый, и к двенадцати годам у него уже росла борода!
«Поедателями углей» называли ни на что не годных, ленивых мальчишек, которые предпочитали лежать у огня и отказывались делать что-либо полезное. Часто они были молчаливыми и хмурыми. Они сильно раздражали отцов, а матери защищали их, уверяя, что рано или поздно из ленивого увальня выйдет толк. Многие скандинавские герои начинали именно так: классический пример – Оффа из Ангельна (Северная Германия), о котором рассказывает Саксон Грамматик. В юности Оффа был молчуном, и его отец Вермунд считал его туповатым простаком. Затем Вермунд ослеп, и соседи-саксы угрожали вторжением в его земли. Вермунд предложил поединок с их правителем, но они ответили, что бороться со слепцом бесчестно. И тут в дело вмешался Оффа. Он сражался с двумя саксами, но его мечи ломались из-за чрезмерной силы удара. Вермунд быстро дал ему свой меч, которым из-за болезни все равно не мог воспользоваться, и с этим оружием (носившим странное имя Скрэп) Оффа одержал победу и прославил англов. В 1926 году в Оксфорде Толкин основал «Общество поедателей углей» – группу по изучению древнескандинавской литературы. Благодаря ему это старинное выражение дошло до наших дней.
Викар дал Старкаду оружие и взял его на свой корабль, чтобы вместе отправиться на поиски убийц Харальда. Король Хордаланда и его воины сражались на совесть, но сводные братья победили их. Старкад при этом был тяжело ранен:
Однако он выжил и в следующие пятнадцать лет был ближайшим другом и правой рукой Викара в мирное и военное время. Ничто не вечно, и в один из набегов Викар решил направиться в Хордаланд на битву. Корабли попали в полосу встречных ветров, и когда бросили деревянные щепки, чтобы узнать волю богов, стало ясно, что Один требует жертвы: кого-то надо повесить. Поразительно, но жребий пал на короля Викара. Все затихли и решили собраться на следующий день, чтобы обсудить, что делать.