Travelling with a criminal history
This article is a travel topic
There is not very much information available on travelling with a criminal history, as most countries don't stop someone from entering because of an insignificant or antiquated criminal history and it is a non issue.
For most countries that give the issue any concern, the relevant information can be found on the their immigration agency website. Many countries do not "welcome" criminals for obvious reasons however, the amount of criminal history it takes to be refused entry into a country (or how long since your last convictions) varies radically from country to country. In North America, even a minor criminal conviction 50 years ago can cause you to be refused entry, while other countries would require a conviction for a violent or serious crime to be refused entry.
In general, a violent or recent criminal conviction may cause entry issues with some countries. If you are on probation or parole you must follow the travel policies set by your probation officer to the letter, leaving the country (or even your county) without permission may result in a violation.
If you travel to a country that inquires about criminal history during the visa or customs process, you must answer truthfully. Any false statements could result in a lengthy or permanent bar to that country, particularly the USA or Canada. Other countries like the UK and its former possessions have a concept of "spent" convictions that do not have to be declared once the conditions for "spent convictions" are met, and that's about the only time you can get away with not answering truthfully.
The United States of America is generally very strict with criminal records, no matter how minor or how long ago it has been. They do not have any concept of "spent" or "pardoned" convictions, meaning you must truthfully answer any questions about criminal convictions, even if your convictions have been spent or pardoned in your country. If you are a citizen of a country that participates in the Visa Waiver Program (VWP), any convictions, un-adjudicated arrests, or even a previously refused visa makes you ineligible to travel on the VWP.
There are numerous crimes that makes you ineligible to enter the US, including "crimes involving moral turpitude." Moral turpitude is a legal concept in the United States for which the definition can seem imprecise and the list of offences, which can vary somewhat by jurisdiction, can include everything from shoplifting to murder.
If you are convicted of a crime involving moral turpitude, you are ineligible to enter the US and little relief exists for this, except in cases deemed to be "purely political offences" which can be open to interpretation by the immigration officer.
Being convicted of an "aggravated felony" is even worse, though just like crimes involving moral turpitude, these also have a very loose definition, therefore the offences can change over time. However, there is absolutely no relief, and anyone deported or excluded for this reason cannot ever enter the US.
Attempting to enter the US after having been previously deported without a proper visa is a serious felony under US law, and is punishable by up to 20 years in prison. The US conducts extensive security checks on all visa applicants.
Visa Office Advisory Opinions
US immigration law is extremely complex, and consular officials often issue decisions without time to fully consult the technical issues of a case, before pushing applicants to pursue a waiver. Although officials benefit from the "sovereignty" of not having their finding of the facts legally questioned, if you are denied a visa it is possible to seek a legal review of the decision if you believe the consular official misapplied the law. Yourself or your attorney may request the US Visa Office in Washington study the case and issue an Advisory Opinion on the inadmissibility finding. The results of the opinion are binding on the embassy or consulate receiving the advice, and are often shorter (6-8 weeks) than the waiver process (6-18 months) which may not be relevant.
While Canada's policies on criminal record is strict, any convictions no matter how minor or how long ago makes anyone inadmissible, it is possible to overcome the inadmissibility by submitting an application for "rehabilitation". This process can take a long time and requires numerous references to prove that you are in fact rehabilitated and that further offences are unlikely. If you do not want to wait that long, and must go to Canada, you may be able to apply for a temporary resident permit, however the reason must be justified and vacations are not considered a justified reason.
Exception for British Citizens
Citizens of the United Kingdom who have convictions considered "spent" under the 1974 Rehabilitation of Offenders Act do not have to apply for "rehabilitation", as they are automatically pardoned under the 1991 Federal Court of Appeals case Canada (Minister of Employment and Immigration) v. Burgon,  due to the similarity of the two countries' legal systems. Guidance issued to border officers in the ENF14 /OP 19 Criminal Rehabilitation Manual specifies: "the UK Rehabilitation of Offenders Act automatically pardons eligible individuals without the person having to apply [for Rehabilitation], if the person has been sentenced to a term of imprisonment of less than 30 months". However, some exceptions to this rule have been witnessed.
United Kingdom has a concept of "spent" conviction and immigration officers wishing to exclude or remove someone on the basis of criminal conviction must prove that the offence is not spent and therefore the person is not rehabilitated. A conviction is "spent" if more than 10 years has passed since imprisonment (if any) between 6 and 30 months. Any imprisonment over 30 month cannot ever be spent and therefore will always count against you. Imprisonment of less than 6 months or fines have an even shorter rehabilitation period (around 5 years or less).
The immigration wishing to deport you, or refuse entry on the basis of criminal conviction must prove that your convictions have not been "spent". The burden of proof is on them, not you so if you were refused entry due to a criminal conviction chances are your offence is not spent. If the offence is spent, then you don't even have to tell them about it and they cannot use it against you even if they do know. For consecutive prison sentences the rehabilitation period would begin at the time you were last in prison, unless the sentence is over 30 months.
Your visa waiver (if available) should not be affected by a spent conviction.
The rules for the EU, specifically the Schengen Area, regarding character concerns is relatively lax. Questions about criminal convictions are not asked when applying for a Schengen visitor/business visas, and border agent and landing cards (there aren't any) don't ask this either. If any officials or forms ask you if you have a criminal history, you still have to answer truthfully, but in general if its not more than 3 years of imprisonment, or crimes involving alien smuggling or drug offences that resulted in more than 2 years of imprisonment, then generally they will not refuse you entry or visa on that ground. Countries like Germany have specific rules that state anyone convicted of an offence relating to public order with a sentence of more than 3 years, a drug offence with a sentence of more than 2 years, and any offence related to alien smuggling is deportable (a "must deport"). Like the UK they are more concerned with offences committed in their country, rather than outside of the EU. Do not lie in any visa application or when answering questions to officials, because in Germany that is a "can deport". Not all countries have the same rule regarding character concern, so some EU countries may be more lax, however Germany is known to be a rather strict country so it is a good guideline on rules for the EU.
Australia and New Zealand
These countries are rather strict regarding character concerns but Australia specifically says "in the last 10 years" so it is not known if convictions more than 10 years old are "spent". There are sporadic sources that suggests that these countries have a concept of "spent" criminal convictions and have rules in place that prohibits officials from obtaining information on spent convictions, but it is not known if it is automatic or it must be applied for like Canada. There are already other concerns that are just as strict such as being deported from any country (New Zealand), health concerns like being HIV positive or even having cancer or diabetes (one person has been refused a visa to New Zealand just for being obese!), that can result in visa being denied, refused entry, or even deported.