Existing power analysis techniques rely on strong adversary models with prior knowledge of the leakage or training data. We introduce side-channel analysis with unsupervised learning (SCAUL) that can recover the secret key without requiring prior knowledge or profiling (training). We employ an LSTM auto-encoder to extract features from power traces with high mutual information with the data-dependent samples of the measurements. We demonstrate that by replacing the raw measurements with the auto-encoder features in a classical DPA attack, the efficiency, in terms of required number of measurements for key recovery, improves by 10X. Further, we employ these features to identify a leakage model with sensitivity analysis and multi-layer perceptron (MLP) networks. SCAUL uses the auto-encoder features and the leakage model, obtained in an unsupervised approach, to find the correct key. On a lightweight implementation of AES on Artix-7 FPGA, we show that SCAUL is able to recover the correct key with 3700 power measurements with random plaintexts, while a DPA attack requires at least 17400 measurements. Using misaligned traces, with an uncertainty equal to 20\% of the hardware clock cycle, SCAUL is able to recover the secret key with 12300 measurements while the DPA attack fails to detect the key.