Андреа, известный под прозвищем Браччо («оружие», возможно, за свою силу), происходил из рода графов Монтоне, знатной фамилии из Перуджи. Он был серьезно ранен и оказался в изгнании после одной из тех кровопролитных междоусобиц, которые привели к сильному опустошению той области и в которых, как правило, был замешан могущественный дом Бальони. Оставшись сиротой, он поступил на службу к Альбериго да Барбьяно. Когда же он наконец возглавил независимый отряд, неудачи преследовали его с самого начала. Он опустился почти до нищенства, и затем, когда ему удалось снова стать на ноги, страшный пожар в Фолиньо уничтожил все, что у него было. Местные жители собрали щедрые пожертвования, чтобы возместить ему утраченное, однако он был вынужден вернуться к Альбериго. Способности обеспечили Браччо благосклонность со стороны его прежнего командира, но это лишь возбудило к нему ожесточенную зависть, ослаблению которой, возможно, его поведение вовсе не способствовало. Альбериго, которого доверенные командиры сумели убедить в неповиновении Браччо, наклеветав на него, распорядился его убить. За него ходатайствовала жена Альбериго, но когда ее просьбы оказались тщетными, она (так велико было ее возмущение совершающимся предательством) предупредила Браччо, и тот немедленно бежал к Папе. Обнаружив свою ошибку, Альбериго сделал все, что было в его силах, чтобы заставить его вернуться, но Браччо ответил, что командующий, который столь бесчестно обращается с преданным офицером, не заслуживает доверия.
Это был не единственный случай, когда Браччо приходилось терпеть подобное обращение; предательство в те времена было делом обычным. Вскоре после этого, в 1409 году, Владислав, король Неаполя, не слишком терзавшийся угрызениями совести, предложил Браччо помочь ему овладеть его родной Перуджей — замысел, который всегда мил сердцу изгнанника. Предложение было принято. Однако жители города в отчаянии обещали королю подчиниться его власти, при условии что тот откажется от услуг сражающихся на его стороне изгоев Перуджи и предаст Браччо смерти. И на этот раз кондотьер вовремя был предупрежден: когда король послал за ним, он отказался прибыть под предлогом недомогания. Владислав, чрезвычайно раздосадованный тем, что его коварные замыслы были раскрыты, послал внушительную армию против кондотьера, которого лишь недавно принял на службу.
Когда Сфорца служил у Альбериго, он обычно сражался за Джан Галеаццо Висконти, могущественного правителя Милана; но когда у него, наконец, появился свой собственный отряд, Сфорца оказался на противоположной стороне, помогая Перудже в ее отчаянной борьбе против вероломного Висконти. Благодаря неукротимому духу перуджийцев ему это удавалось в течение двух лет. Как и в политике, военный успех был одним из лучших способов обратить внимание начальства на достоинства воина. Джан Галеаццо, в его неутомимом стремлении создать сильное независимое королевство на севере Италии, решил нанять к себе на службу лучших кондотьеров, и вскоре Сфорца стал сражаться на его стороне, получая жалованье вдвое большее, чем прежде. Но, как и в случае с Браччо, успех пробудил зависть, и распространившиеся клеветнические слухи о нем привели к его позорной отставке со службы в Милане. Положение Сфорца оказалось настолько опасным, что ему пришлось бежать, спасая свою жизнь.
После этого Сфорца поступил на службу Флоренции, воевавшей против Пизы, которую защищал его бывший командир, Альбериго да Барбьяно. Здесь началась его долгая распря с кондотьером Тартальей, тоже состоявшим на жалованье у Флоренции. Одно время вражда между ними была столь острой, что казалось вполне вероятным, что они обратят свое оружие не против врага, а друг против друга, и возникла необходимость развести их войска вместе с их лидерами в разные стороны. Союзник Флоренции Рупрехт, Римский король, полностью разделял высокое мнение о достоинствах Сфорца, проявив свое расположение тем, что позволил ему использовать свой собственный герб — льва, стоящего на задних лапах. Сообщается также о том, что именно он посоветовал изображать льва, держащего в лапе айвовую ветвь (котинью), эмблему родного города Сфорца, которой он пользовался до тех пор. В окончательном варианте на гербовом щите был также изображен шлем Сфорца с крылатым драконом с человеческой головой.
Приблизительно в это же время Сфорца познакомился с Лючией Трегани, или Лючией ди Терцано, девушкой благородного происхождения, которая многие годы оставалась его любовницей. Она родила ему по меньшей мере семь детей, среди которых был и его наследник, Франческо, будущий герцог Милана, родившийся в Сан-Миньято 23 июля 1401 года. Говорили, что он покорил сердце Лючии своей преданной любовью к ней и обещанием жениться, но поскольку брачные законы в то время были весьма неопределенны, ее положение было немногим менее стабильным, чем у законной супруги.