Originally defined high-entropy alloys (HEAs) are generally in a solid-solution state, which are solution-strengthened by multiple-elements with desired toughness. However, the mixture of multiple elements likely result in certain microstructure features, which could also benefit the HEAs. In this study, AlCrFeCoNi and AlCrFeCoNiTi0.5 high entropy alloys (HEAs) were fabricated, and their microstructures and sliding wear behaviors (in comparison with stainless steel) were investigated using XRD, SEM, EDS and a pin-on-disc tribometer, respectively. It is shown that the two HEAs consist of ordered Al–Ni/Al–Ni–Ti rich BCC and disordered Fe–Cr rich BCC domains. The AlCrFeCoNi alloy has an intertwined structure with plate-like Fe–Cr rich domains embedded in the Al–Ni rich matrix. The AlCrFeCoNiTi0.5 alloy shows a similar microstructure but has honeycomb-like Fe–Cr rich interdendrites. The Ti addition markedly increases the hardness of the alloy, leading to considerably enhanced resistance to sliding wear. Through wear tests with and without air-flow to minimize frictional heating along with worn surface analysis, we demonstrate that the Ti addition also enhances the oxide scale, making additional contribution to the wear resistance.