I can think of a few ways to help establish party cohesion:
Flashback Adventure
Pause the main story. Pick a character with a suitable backstory, and explain that we're going to do a quick one-shot from before the adventure began.
For instance, Sheila the Sly was a member of the Freeport Thieves Guild, along with Rexx the Enforcer. The new character, Lorenzo the Duelist, spent time in Freeport, so we can use this as a setting. The party's other two members have never been to Freeport, so we hand those players pre-rolled characters: Guild Lieutenant Tambrere and Ekatarina Stormfist.
The scene we are playing out has Ekatarina and Lorenzo crossing through Freeport at dusk. Lorenzo is a bodyguard, working for Ekatarina the Sorcerer. They are trying to reach her father's ship ahead of a team of assassins, and after weeks of hard travel the end is in sight...when the Bloody Billhooks step out of the shadows.
The Billhooks don't know anything about the Dread Curse, or the Sceptre, or the bounty - They just see a couple of well-off marks that nobody will miss. The leader is overconfident, calling out to his minions about the easy score to make sure they are in good spirits. They have them outnumbered eight to two - bad odds for anyone.
After the first round, we cut to the Thieves Guild, watching from the rooftops. The Billhooks are murderous marauders, at war with the Thieves Guild, and Tambere has orders to cause them trouble or take them out if the opportunity arises. Three-on-eight didn't look like an opportunity; Five on eight just might do it.
...and from there, run the scene to a satisfying conclusion and cut back to present day. Sheila and Rexx will be pleased to see Lorenzo again, everyone has a good time, and you got the chance to do some worldbuilding. Maybe down the road Ekatarina joins the party, or the Stormfist family reaches out for a favor. By casting the Billhooks as the ugly version of the Thieves Guild, we flesh out that organization, as well as setting up a potential adversary for future stories.
Friends in High Places
If the mission has a sponsor, like a king or merchant, it is reasonable that they send someone to check up on you. Maybe a Chamberlain catches up to the party with an Alchemist and a few bodyguards. The Alchemist does some healing and trades for potions, the Chamberlain collects a report and provides some new information, and after hearing that the party has lost a member suggests that one of the bodyguards take their place.
This gives you the opportunity to have a trusted third party introduce the character. "Ralphonzo is a little rough around the edges, but I've never met a better fighting-man. He took down a Griffon all but single-handedly on our journey here, and wears the pelt as a cape as proof."
In higher-level campaigns, you could have a court wizard open a Dimension Door to visit the heroes, again serving as a resupply and reinforce visit. If your campaign relies on attrition, this might be less useful, but used infrequently can really open up the world.
Last Survivor
The party enters a battlefield. The air is thick with the crackle of spells, blood and ichor befoul the floor, and everywhere destruction and death marks the area. One last survivor of the battle still draws breath.
If you want to raise the stakes and convince the players they are up against a serious threat, nothing sells it quite like seeing someone else that didn't overcome it. Use this scene to raise the drama, and clue the characters in to what they face. The other adventurers have probably already been looted or devoured, but it's possible that some useful gear was left behind. Also possible it's haunted or cursed - there's good reason not to disturb the dead.
The nature of the other adventurers is also a good opportunity for filling out the world. If you plan to have the party visit a neighboring kingdom, maybe one or more of the fallen are from there. Maybe some of the adventurers were NPCs we know from before, or are members of groups we know. A Dwarven Stonebreaker, a cleric of an unpopular god, a Gnomish trapmaster...you can introduce or build out anything that you want the players to know better.
And of course, the only one who knows who these people are, how they died, and how the PCs might do better is the new character. With just a little help, they might even be able to get revenge.