The late Tom Landry in his autobiography (page 129) wrote how the rivalry began - even before the Cowboys were a team:
It seems a short while before, {Washington Redskin owner} George Marshall had fired his band director who had composed Washington's official fight song, "Hail to the Redskins." To spite Marshall, the musician sold the copyright for the song to a lawyer who also had some differences with Marshall in the past. And the new owner of the copyright just happened to be one of {future Dallas Cowboy owner} Clint Murchison's lawyers.
So after two days of haggling over expansion, Marshall, who had always been especially fond of his team's fight song, agreed to vote in favor of the Dallas franchise if Clint's lawyer would give him back the rights to "Hail to the Redskins." An agreement to that effect was quickly drawn up and signed, and Dallas was voted into the NFL on January 28, 1960 - Alicia's and my eleventh wedding anniversary.