Every function in a living cell is accomplished by proteins interactions. The capability of predicting such interactions gives greater insight in the study of many diseases and provides valuable information in the study of active small molecules. Here, we formulate the problem as a binary task on information extracted only from amino acid sequences. We apply a k-Nearest Neighbors classification technique to the classes of interacting and noninteracting proteins, providing evidence it is possible to predict interactions efficiently. Furthermore, we show that feature selection can greatly influence performance of the method. A real life case study is analyzed to show the method provides results that can be comparable with those obtained with other techniques.