We release the AllWISE counterparts and Gaia matches to 106,573 and 17,665 X-ray sources detected in the ROSAT 2RXS and XMMSL2 surveys with |b|>15. These are the brightest X-ray sources in the sky, but their position uncertainties and the sparse multi-wavelength coverage until now rendered the identification of their counterparts a demanding task with uncertain results. New all-sky multi-wavelength surveys of sufficient depth, like AllWISE and Gaia, and a new Bayesian statistics based algorithm, NWAY, allow us, for the first time, to provide reliable counterpart associations. NWAY extends previous distance and sky density based association methods and, using one or more priors (e.g., colors, magnitudes), weights the probability that sources from two or more catalogues are simultaneously associated on the basis of their observable characteristics. Here, counterparts have been determined using a WISE color-magnitude prior. A reference sample of 4524 XMM/Chandra and Swift X-ray sources demonstrates a reliability of ~ 94.7% (2RXS) and 97.4% (XMMSL2). Combining our results with Chandra-COSMOS data, we propose a new separation between stars and AGN in the X-ray/WISE flux-magnitude plane, valid over six orders of magnitude. We also release the NWAY code and its user manual. NWAY was extensively tested with XMM-COSMOS data. Using two different sets of priors, we find an agreement of 96% and 99% with published Likelihood Ratio methods. Our results were achieved faster and without any follow-up visual inspection. With the advent of deep and wide area surveys in X-rays (e.g. SRG/eROSITA, Athena/WFI) and radio (ASKAP/EMU, LOFAR, APERTIF, etc.) NWAY will provide a powerful and reliable counterpart identification tool.