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