Functional connectivity expresses the correlation of brain activity between regions and helps in understanding and diagnosing neurological conditions and disorders. It also provides discriminative features for machine learning classifiers. We propose a model-agnostic method that produces realistic counterfactual functional connectomes by altering the posterior distribution of a hierarchical variational auto-encoder and de-noising the result. We evaluate our method on three autism spectrum disorder classifiers for resting state fMRI. The generated counterfactuals include plausible changes in line with medical literature and the brain’s functional anatomy. Our approach strives for explainability and collaboration with medical experts, starting from the model selection.