Combine History

Spoiler warning: Plot and/or ending details follow.

Introduction

The Combine are apparently led by a group of Advisors such as the one seen talking to Dr. Breen in Half-Life 2.

The Combine is an intergalactic (or possibly interdimensional, or both) alliance of species. Its true nature is not very well known. What we do know is this:

The Combine were in fact NOT on Xen at the beginning of Half-Life. This was recently stated by Doug Lombardi.
The creatures on Xen were there because they had been running from the Combine, and Xen was a refuge.
The dimensional rift caused by the resonance cascade attracted the Combine to Earth. It only took them seven hours to completely take over Earth, hence the invasion's name: § The 7 Hour War.
After the invasion, Dr. Wallace Breen, the Black Mesa Research Facility administrator, brokered a "peace" with the Combine and convinced them that Humanity could be evolved and assimilated into the Combine. Dr. Breen worked with the Combine to produce "trans-humans", mostly in the form of Combine Soldiers.
The Combine had at least one Citadel at the beginning of Half-Life 2. It's possible there may be more, possibly one for each of the cities, cities 9 through 20 at least, mentioned at the beginning.
The only other race apart from the natives of Xen and Transhumans is the race of the Combine Advisor.

Xen: Before Half-Life

Before Half-Life, the Combine were already an interstellar threat. The Xenians were made up of many races of alien species that were conquerors at one point, and then sought refuge from the Combine destruction. The Vortigaunts were slaves to the Nihilanth, but the Nihilanth also has metal wristbands similar to those of the Vortigaunts, and it has what appear to be surgical scars. The Nihilanth's legs have also been amputated (similar to the Stalkers). This signifies that the Combine may have enslaved the Nihilanth at one point. Although they were not on Xen, the Combine had there fair share of influence before the resonance cascade. More than this cannot be said.

Black Mesa Research Facility

Because the Combine were not on Xen, we can't say anything about the Black Mesa incident except that it attracted the Combine to Earth.

Gordon Freeman and Xen

There isn't a whole lot that can be said here either, but there is evidence of a "greater threat" in the original game. Although you don't meet this threat in Half-Life, the Nihilanth hints at the existence of the Combine. For more info, see Wikipedia:Nihilanth.

The 7 Hour War

The 7 Hour War is the name given to the military invasion of Earth by the Combine. It seems that Earth's forces were overwhelmed and almost, if not totally, annihilated in 7 Hours. After this Breen brokered peace. See Wikipedia:Seven Hour War for more information.

“Dr. Breen...

He's the Administrator of this whole vile business now.

He ended the Seven Hours War by managing Earth's surrender.

The Combine rewarded him with power.” — Eli Vance

The World After That

After the Combine invaded Earth and established the Overwatch to police its inhabitants, Breen began oppressing humanity on the behalf of his Combine overlords. While no one knows the exact nature of the activities the Combine were engaged in, they may have included some of the following: