I've always used Visa but after seeing some useful travel cards from Mastercard & American Express; I was wondering whether they would be useful at all if they aren't accepted widely. Out of the two which one has a wider acceptance especially in Europe.
Mastercard, hands down. If you want a card to make payments abroad, your choice is between Mastercard and Visa, especially in Europe. Other cards are much less commonly accepted (and in fact quite rare there).
American Express cards can be good for their perks: cash back, insurance, miles, rewards, whatever but not for convenience when travelling… You could perhaps get an Amex to complement your Visa but certainly not switch and rely solely on it.
Importantly, unlike acceptance, perks also depend on the bank/institution and the type of card, rather than only on the network so there are several level of American Express and also some Visa or Mastercards with useful perks like travel assurance. If that's what you are after, you need to read the fine print and compare specific cards very carefully.
The answer is almost certainly MasterCard, but this is a poor basis on which to decide between the two.
You're right to intuit that American Express is accepted less often than Visa or MC. This is largely because AmEx charges a higher fee to merchants for transactions, and because the cards themselves are generally less common. AmEx is also only accepted in 140 countries, compared to the 200+ in which Visa and MasterCard operate. That said, I'd still call it 'widely accepted', and AmEx cards often offer a host of benefits that other cards often won't match, particularly in the realm of purchase protection and travel insurance.
Mastercard and Visa are accepted at just about equal rates around the world. In general, if you can use one, the other will work. The thing about both, is that neither is issued by a bank, and so, the benefits of a particular Visa or MasterCard option will vary wildly. Thus, it's a bit silly to limit the conversation to comparisons of the individual networks when talking about a Visa or MC, because a Chase Visa Sapphire card is so wildly different from, say, a Chase Student Rewards card. From interest rates to purchase protection to rewards, literally almost everything about any two Visa or MasterCard issued cards can be different.
In general, the only notable network-wide differences between Visa and Mastercard are as follows: Visa offers you substantially better protections than MC when used to pay for a rental car. MasterCard offers you price protection and guarantees your ability to return merchandise within 60 days. Individual Visa or MasterCard offerings through a specific bank may offer benefits and services that exceed either of these baselines, and, for example, may make an individual MC offering a better choice for use on a rental car, even though the MasterCard network as a whole is not.
TL;DR: If you're concerned about acceptance, it's important that you probably have at least one Visa or MasterCard, which it sounds like you already do. For any further cards beyond that, look at the specific perks and protections and benefits of an individual card, and don't worry too much about acceptance rate. And remember, it's always good to carry some cash. It has an acceptance rate closer to 100% than any alternatives.
Having worked a bit in retail since the 90s and my wife having a pub for a while, I can say that at least in Germany, Mastercard is the most accepted one (alongside Visa, you almost nowhere see only one of those two, usually bank contracts are in a such way that when you want to accept one, you basically get the other one for the same transaction fee without any further costs). In some areas you have to search quite hard for AmEx being accepted.
Why is that so? I remember that in the late 90s the shop I was working in stopped supporting AmEx because they raised transaction fees. Again. Also depending on the contract you had with your bank, I can remember that a few years ago AmEx costs for certain transaction price ranges common in pubs was 3 to 5 times as much as for Visa/Mastercard.
I have hardly any solid base for other countries in europe, let alone other continents, but it seems that in europe Amex is not much represented elsewhere either.
A lot of the other answers are recommending MasterCard, but actually, Visa holds the largest market share among card networks (49.3%) versus MasterCard's 30.8% or American Express's 9.2%. The difference is even more pronounced for debit cards with Visa holding a majority over MasterCard. American Express does not offer debit cards. (The analysis linked to is based on financial report filings at the end of 2013; older analysis from 2010 with similar conclusions here as well.)
In general, you'll find either Visa or MasterCard is accepted more widely than Amex, especially across Europe which you're interested in.
Anecdotally - at least from my experience in the UK - chain stores, restaurants, bars etc. are much more likely to accept American Express as they probably get larger transaction fee discounts on their merchant accounts.
Most of the answers are already correctly responding to your question, but I'd like to chip in with my personal experience.
When I was living in Canada 3 years ago, Amex was supported by half businesses that were supporting credit card payments. The reasons behind it is that Amex charges higher fees to the businesses so they prefer to support other cards first. It is more likely to see Amex support in big hotels or places offering very pricey stuff, as the transaction ceilings are way higher.
I now live in France, and the same statement turns out to be true.
Travel-wise, the best tip I can give to a traveling couple is that one should have Visa, the other MasterCard. Unless you have a huge wallet, Amex will not be very useful to you.
I may relate to places where I travelled to or lived in.
Around the world, Visa > Master Card >> Amex. In many places they don't accept Amex at all.
Germany: they use Maestro circuit debit cards a lot. Those are really common, the next choice after cash.
France: they do accept "Maestro like" debit cards but they are not as common nor work as good. I could not get my Maestro card accepted by half the places (shops, gas stations...). Also, I could not pay their many toll highways if not with cash or VISA / Vanilla Master Card.
Italy: they accept Maestro and Maestro white label cards in a LOT of places, more often than where they accept credit cards. Italy got some seriously weird laws so carrying and paying with cash may be difficult. If you go with a Maestro card, check it's accepted by ATMs, they have some ATM circuits that don't take all the white labels, expecially in the south. VISA is accepted the most, Master Card tends to work but not all the varieties, make sure to have a the most standard Master Card possible. Amex is accepted in some hotels and restaurants and not elsewhere.
Spain: they accept Maestro expecially in the turistic locations. They also accept some common white labels. VISA and Mastercards are widely accepted expecially in the turistic locations. Amex is accepted at hotels and restaurants, I have talked with some shop owners and they all complained Amex charges more so they tend to not support it. Banks tend to give Master Card debit cards, Maestro is supported expecially because a lot of German tourists go to certain turistic places (in example: Canary Islands).
When it comes to creditcards, the existing answers already point out that Mastercard and Visa are the most commonly accepted cards in europe.
However, what should be noted is the following:
In Europe credit cards are not as widely accepted as in the US
If you want to spend your time shopping in big tourist centers, or renting cars, you should be fine with a creditcard. However, if you also want to pay in smaller stores, supermarkets, or restaurants, you may find that they do not accept credit cards.
If you don't specifically need a creditcard, but just want to pay things wherever you go in europe, the following is important to note:
Cash is the most commonly accepted payment method - after that, Maestro in the Netherlands/Germany but Visa/MC of any kind elsewhere
Maestro actually is not even offered at all outside of certain northern European countries (phased out entirely in France about 10 years ago for example).