In our world, a man might have a pretty bad time of it if he tried to go about his everyday business without a physical heart in his chest. In the magical land of Ingary, by contrast, Howl's main trouble living without a heart is that he loses some essence of his soul, which he gets back when Sophie breaks his contract with Calcifer. The heart is highly symbolic in this novel, representing all of the usual Valentine's Day sentiments about love and caring for other people—and without his, we see that Howl struggles a lot with his love life.
When Sophie asks Howl why he is so unreliable with women—why he pursues them just long enough to win their affections and then drops them—he tells her he keeps trying to find love, but "I brought it on myself by making a bargain some years ago, and I know I shall never be able to love anyone properly now" (14.86). Howl's lost heart prevents him from settling down with a lady, and it's only when his contract with Calcifer is broken that he can really propose that traditional fairytale happy ending to a newly young Sophie.
But here's the funny thing—yes, Howl's fickle nature with ladies seems to have to do with his missing heart. After all, the other person in this novel who has given up her heart to a fire demon—the Witch of the Waste—actually tries to assemble her perfect man from the bodies of three different dudes. Clearly love is a problem if you are a magic-user with a fire demon using your heart to prolong its life.
At the same time though, we find out later that Howl only meets with Lettie to find out more about Sophie when he's trying to crack Sophie's curse. And Miss Angorian? Howl has known all along that she is the Witch of the Waste's fire demon. Howl's fickle nature turns out to be a cover for his longstanding, intense interest in Sophie. Sure once his heart is properly restored he and Sophie can get together freely, but before then Howl seems to have had enough access to his inner romantic to fall in love with Sophie anyway, even without a heart beating in his chest.